public class Sort {

    //交换元素
    public static void swap(int[] arr,int a,int b) {
        int ret = arr[a];
        arr[a] = arr[b];
        arr[b] = ret;
    }

    //选择排序
    public static void select(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while(left < right) {
            int min = left;
            int max = left;
            for (int i = left + 1; i <= right ; i++) {
                if(arr[i] < arr[min]) {
                    min = i;
                }
                if(arr[i] > arr[max]) {
                    max = i;
                }
            }
            swap(arr,left,min);
            if(left == max) {
                max = min;
            }
            swap(arr,right,max);
            left++;
            right--;
        }
    }

    //堆排序
    public static void isDui(int[] arr) {
        creaHeap(arr);
        int end = arr.length-1;
       while(end > 0) {
           swap(arr,0,end);
           siftDown(arr,0,end);
           end--;
       }
    }

    public static void creaHeap(int[] arr) {
        for (int i = (arr.length-1-1) / 2; i >= 0 ; i--) {
            siftDown(arr,i,arr.length);
        }
    }

    public static void siftDown(int[] arr,int root,int k) {
        int child = 2 * root+1;
        while(child < k) {
            if(child + 1 < k && arr[child+1] > arr[child]) {
                child++;
            }
            if(arr[root] < arr[child]) {
                swap(arr,root,child);
            }else {
                break;
            }
            root = child;
            child = 2 * root+1;
        }
    }

    //冒泡排序
    public static void Maopao(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            boolean k = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                    k = true;
                }
            }
            if(!k) {
                break;
            }
        }
    }

    //快速排序（Hoare法）
    public static void fast1(int[] arr) {
        fast2(arr,0,arr.length-1);
    }

    public static void fast2(int[] arr,int start,int end) {
        if(start >= end) {
            return;
        }
        int ret = fastHoare(arr,start,end);

        fast2(arr,start,ret-1);

        fast2(arr,ret+1,end);
    }

    public static int fastHoare(int[] arr,int left,int right) {
        int i = left;
        int tem = arr[left];
       while(left < right) {
           while (left < right && arr[right] >= tem) {
               right--;
           }
           while (left < right && arr[left] <= tem) {
               left++;
           }
           swap(arr, left, right);
       }
       swap(arr,i,left);
       return left;
    }

    //快速排序（挖坑法）
    public static void fastone(int[] arr) {
        fasttwo(arr,0,arr.length-1);
    }

    public static void fasttwo(int[] arr,int start,int end) {
        if(start >= end) {
            return;
        }
        int ret = fastWakeng(arr,start,end);

        fasttwo(arr,start,ret-1);

        fasttwo(arr,ret+1,end);
    }

    public static int fastWakeng(int[] arr,int left,int right) {
        //int i = left;
        int tem = arr[left];
        while(left < right) {
            while (left < right && arr[right] >= tem) {
                right--;
            }
            arr[left] = arr[right];

            while (left < right && arr[left] <= tem) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tem;
        return left;
    }

/////////////////////////////////////////////////////////////////////////////

    // 选择排序
    public static void selectSort(int[] arr){
        // write code  here
        int left = 0;
        int right = arr.length-1;
        while(left < right) {
            int min = left;
            int max= left;
            for (int i = left+1; i <= right; i++) {
                if(arr[min] > arr[i]) {
                    min = i;
                }
                if(arr[max] < arr[i]) {
                    max = i;
                }
            }
            swap(arr,left,min);
            if(left == max) {
                max = min;
            }
            swap(arr,max,right);
            left++;
            right--;
        }
    }


    // 堆排序
    public static void heapSort(int[] arr){
        // write code  here
        kk(arr);
        int end = arr.length-1;
        while(end > 0) {
            swap(arr,0,end);
            Xiangxia(arr,0,end);
            end--;
        }

    }

    public static void kk(int[] arr) {
        for (int i = (arr.length-1-1) / 2; i >= 0 ; i--) {
            Xiangxia(arr,i,arr.length);
        }
    }

    public static void Xiangxia(int[] arr,int root,int k) {
        int child = 2 * root +1;
        while(child < k) {
            if(child +1 < k && arr[child+1] > arr[child]) {
                child++;
            }
            if(arr[child] > arr[root]) {
                swap(arr,root,child);
            }else {
                break;
            }
            root = child;
            child =  2 * root+1;
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] arr){
        // write code  here
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }

    // 快速
    public static void quickSort(int[] arr){
        // write code  here
        quickSort2(arr,0,arr.length-1);
    }

    public static void quickSort2(int[] arr,int start,int end) {
        if(start >= end) {
            return;
        }
        int ret = quickSort3(arr,start,end);

        quickSort2(arr,start,ret-1);

        quickSort2(arr,ret+1,end);
    }

    public static int quickSort3(int[] arr,int left,int right) {
        int i = left;
        int tem = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= tem) {
                right--;
            }
            while(left < right && arr[left] <= tem) {
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,i);
        return left;
    }

    //归并排序
    public static void guibing(int[] arr) {
        gui2(arr,0,arr.length-1);
    }

    public static void gui2(int[] arr,int left,int right) {
        if(left == right) {
            return;
        }

        int mid = (left + right) / 2;

        gui2(arr,left,mid);

        gui2(arr,mid + 1,right);

        //开始合并排序
        gui3(arr,left,mid,right);

    }

    public static void gui3(int[] arr,int left,int mid,int right) {
        
        int[] array = new int[right - left + 1];
        int k = 0;
        
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        
        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] > arr[s2]) {
                array[k++] = arr[s2++];
            }else {
                array[k++] = arr[s1++];
            }
        }

        while(s1 <= e1) {
            array[k++] = arr[s1++];
        }

        while(s2 <= e2) {
            array[k++] = arr[s2++];
        }

        for (int i = 0; i < k; i++) {
            arr[i+left] = array[i];
        }
    }


    //归并排序（非递归）
    public static void isgui(int[] arr) {
        int gap = 1;
        while(gap < arr.length) {
            for (int i = 0; i < arr.length; i++) {
                int left = i;
                int mid = left + gap - 1;
                if(mid > arr.length) {
                    mid = arr.length;
                }
                int right = mid + gap;

                if(right > arr.length) {
                    right = arr.length;
                }

                gui3(arr,left,mid,right);
            }
            gap *=2;
        }
    }

    //计数排序
    public static void jishu(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < min) {
                min = arr[i];
            }
            if(arr[i] > max) {
                max = arr[i];
            }
        }

        int len = max - min + 1;
        int[] array = new int[len];
        for (int i = 0; i < array.length; i++) {
            int index = arr[i]-min;
            array[index]++;
        }

        int k = 0;
        for (int i = 0; i < array.length; i++) {
            while(array[i] != 0) {
                arr[k] = i+min;
                k++;
                array[i]--;
            }
        }
    }




    // 归并排序---递归
    public static void mergeSort1(int[] arr){
        // write code  here
        merges(arr,0,arr.length-1);
    }

    public static void merges(int[] arr,int left,int right) {
        if(left == right) {
            return;
        }

        int mid = (left + right) / 2;

        merges(arr,left,mid);

        merges(arr,mid+1,right);

        mer(arr,left,mid,right);
    }

    public static void mer(int[] arr,int left,int mid,int right) {

        int k = 0;
        int[] array = new int[right - left + 1];

        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;

        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] > arr[s2]) {
                array[k++] = arr[s2++];
            }else {
                array[k++] = arr[s1++];
            }
        }
        while(s1 <= e1) {
            array[k++] = arr[s1++];
        }
        while(s2 <= e2) {
            array[k++] = arr[s2++];
        }

        for (int i = 0; i < k; i++) {
            arr[i+left] = array[i];
        }
    }

    // 归并排序---非递归
    public static void mergeSort2(int[] arr){
        // write code  here
        int gap = 1;
        while(gap < arr.length) {
            for (int i = 0; i < arr.length; i += 2*gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid > arr.length) {
                    mid = arr.length-1;
                }
                int right = mid + gap;
                if(right > arr.length) {
                    right = arr.length-1;
                }

                mer(arr,left,mid,right);
            }
            gap *=2;
        }
    }

    // 计数排序
    public static void countSort(int[] arr){
        // write code  here
        int min = arr[0];
        int max = arr[0];

        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < min) {
                min = arr[i];
            }
            if(arr[i] > max) {
                max = arr[i];
            }
        }

        int len = max - min + 1;
        int[] array = new int[len];
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i]-min;
            array[index]++;
        }

        int k = 0;
        for (int i = 0; i < array.length; i++) {
            while(array[i] != 0) {
                arr[k] = i+min;
                k++;
                array[i]--;
            }
        }
    }
}
